package com.lw.leetcode.sort.b;

import com.lw.test.util.Utils;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * sort
 * 1834. 单线程 CPU
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/25 11:28
 */
public class GetOrder {

    public static void main(String[] args) {
        GetOrder test = new GetOrder();

        // {0,2,3,1}
//        int[][] tasks = {{1, 2}, {2, 4}, {3, 2}, {4, 1}};

        // {4,3,2,0,1}
//        int[][] tasks = {{7, 10}, {7, 12}, {7, 5}, {7, 4}, {7, 2}};

        //
        int[][] tasks = Utils.getArr(10000, 2, 1, 1000000000);

//        int[] order = test.getOrder(tasks);
//        System.out.println(Arrays.toString(order));
    }

    public int[] getOrder(int[][] tasks) {
        int length = tasks.length;
        int[][] items = new int[length][3];
        for (int i = 0; i < length; i++) {
            items[i][0] = tasks[i][0];
            items[i][1] = tasks[i][1];
            items[i][2] = i;
        }
        Arrays.sort(items, (a, b) -> a[0] == b[0] ? (a[1] == b[1] ?
                Integer.compare(a[2], b[2]) : Integer.compare(a[1], b[1])) : Integer.compare(a[0], b[0]));
        long time = 0;
        PriorityQueue<Long> times = new PriorityQueue<>();
        int[] values = new int[length];
        int index = 0;
        for (int i = 0; i < length; i++) {
            int[] task = items[i];
            if (task[0] <= time) {
                times.add(((long) task[1] << 17) + task[2]);
            } else {
                if (times.isEmpty()) {
                    time = task[0];
                    times.add(((long) task[1] << 17) + task[2]);
                    continue;
                }
                Long p = times.poll();
                time += (p >> 17);
                values[index++] = (int) (p & 0X1FFFF);
                i--;
            }
        }
        while (!times.isEmpty()) {
            values[index++] = (int) (times.poll() & 0X1FFFF);
        }
        return values;
    }

}
